package tools

import (
	"errors"
	"fmt"
	"strconv"
	"strings"
)

const (
	// Literal 字面量，e.g. 50
	Literal = iota
	// Operator 操作符, e.g. + - * /
	Operator
)

type Token struct {
	// 原始字符
	Tok string
	// 类型，有 Literal、Operator 两种
	Type   int
	Offset int
}

// Parser 定义一个结构体，描述一个词法分析器
type Parser struct {
	// 输入的字符串
	Source string
	// 扫描器当前所在的字符
	ch byte
	// 扫描器当前所在的位置
	offset int
	// 扫描过程出现的错误收集
	err error
}

// 逐个字符扫描，得到一串 Token 序列
func (p *Parser) parse() []*Token {
	tokens := make([]*Token, 0)
	// 一直获取下一个 Token
	for {
		tok := p.nextTok()
		if tok == nil {
			// 已经到达末尾或者出现错误时，停止
			break
		}
		// 收集 Token
		tokens = append(tokens, tok)
	}
	return tokens
}

// 获取下一个 Token
func (p *Parser) nextTok() *Token {
	// 已经到达末尾或者出现错误
	if p.offset >= len(p.Source) || p.err != nil {
		return nil
	}
	var err error
	// 跳过所有无意义的空白符
	for p.isWhitespace(p.ch) && err == nil {
		err = p.nextCh()
	}
	start := p.offset
	var tok *Token
	switch p.ch {
	// 操作符
	case
		'(',
		')',
		'+',
		'-',
		'*',
		'/',
		'^',
		'%':
		tok = &Token{
			Tok:  string(p.ch),
			Type: Operator,
		}
		tok.Offset = start
		// 前进到下一个字符
		err = p.nextCh()

		// 字面量(数字)
	case
		'0',
		'1',
		'2',
		'3',
		'4',
		'5',
		'6',
		'7',
		'8',
		'9':
		for p.isDigitNum(p.ch) && p.nextCh() == nil {
		}
		tok = &Token{
			Tok:  strings.ReplaceAll(p.Source[start:p.offset], "_", ""),
			Type: Literal,
		}
		tok.Offset = start

		// 捕获错误
	default:
		if p.ch != ' ' {
			s := fmt.Sprintf("symbol error: unkown '%v', pos [%v:]\n%s",
				string(p.ch),
				start,
				ErrPos(p.Source, start))
			p.err = errors.New(s)
		}
	}
	return tok
}

// 前进到下一个字符
func (p *Parser) nextCh() error {
	p.offset++
	if p.offset < len(p.Source) {
		p.ch = p.Source[p.offset]
		return nil
	}
	// 到达字符串末尾
	return errors.New("EOF")
}

// 空白符
func (p *Parser) isWhitespace(c byte) bool {
	return c == ' ' ||
		c == '\t' ||
		c == '\n' ||
		c == '\v' ||
		c == '\f' ||
		c == '\r'
}

// 数字
func (p *Parser) isDigitNum(c byte) bool {
	return '0' <= c && c <= '9' || c == '.' || c == '_' || c == 'e'
}

// ErrPos 对错误包装，进行可视化展示
func ErrPos(s string, pos int) string {
	r := strings.Repeat("-", len(s)) + "\n"
	s += "\n"
	for i := 0; i < pos; i++ {
		s += " "
	}
	s += "^\n"
	return r + s + r
}

// NewAST 生成一个 AST 结构指针
func NewAST(tokens []*Token, s string) *AST {
	a := &AST{
		Tokens: tokens,
		source: s,
	}
	if a.Tokens == nil || len(a.Tokens) == 0 {
		a.Err = errors.New("empty token")
	} else {
		a.currIndex = 0
		a.currTok = a.Tokens[0]
	}
	return a
}

// ExprAST 基础表达式节点接口
type ExprAST interface {
	toStr() string
}

// NumberExprAST 数字表达式节点
type NumberExprAST struct {
	// 具体的值
	Val float64
}

// BinaryExprAST 操作表达式节点
type BinaryExprAST struct {
	// 操作符
	Op string
	// 左右节点，可能是 数字表达式节点/操作表达式节点/nil
	Lhs,
	Rhs ExprAST
}

// 实现接口
func (n NumberExprAST) toStr() string {
	return fmt.Sprintf(
		"NumberExprAST:%s",
		strconv.FormatFloat(n.Val, 'f', 0, 64),
	)
}

// 实现接口
func (b BinaryExprAST) toStr() string {
	return fmt.Sprintf(
		"BinaryExprAST: (%s %s %s)",
		b.Op,
		b.Lhs.toStr(),
		b.Rhs.toStr(),
	)
}

// Parse 封装词法分析过程，直接调用该函数即可解析字符串为[]Token
func Parse(s string) ([]*Token, error) {
	// 初始化 Parser
	p := &Parser{
		Source: s,
		err:    nil,
		ch:     s[0],
	}
	// 调用 parse 方法
	tokens := p.parse()
	if p.err != nil {
		return nil, p.err
	}
	return tokens, nil
}

// ExprASTResult 一个典型的后序遍历求解算法
func ExprASTResult(expr ExprAST) float64 {
	// 左右值
	var l, r float64
	switch expr.(type) {
	// 传入的根节点是 BinaryExprAST
	case BinaryExprAST:
		ast := expr.(BinaryExprAST)
		// 递归左节点
		l = ExprASTResult(ast.Lhs)
		// 递归右节点
		r = ExprASTResult(ast.Rhs)
		// 现在 l,r 都有具体的值了，可以根据运算符运算
		switch ast.Op {
		case "+":
			return l + r
		case "-":
			return l - r
		case "*":
			return l * r
		case "/":
			if r == 0 {
				panic(errors.New(
					fmt.Sprintf("violation of arithmetic specification: a division by zero in ExprASTResult: [%g/%g]",
						l,
						r)))
			}
			return l / r
		case "%":
			return float64(int(l) % int(r))
		default:
		}
		// 传入的根节点是 NumberExprAST,无需做任何事情，直接返回 Val 值
	case NumberExprAST:
		return expr.(NumberExprAST).Val
	}
	return 0.0
}

// 定义操作符优先级，value 越高，优先级越高
var precedence = map[string]int{"+": 20, "-": 20, "*": 40, "/": 40, "%": 40, "^": 60}

// ParseExpression 语法分析器入口
func (a *AST) ParseExpression() ExprAST {
	lhs := a.parsePrimary()
	return a.parseBinOpRHS(0, lhs)
}

// 获取下一个 Token
func (a *AST) getNextToken() *Token {
	a.currIndex++
	if a.currIndex < len(a.Tokens) {
		a.currTok = a.Tokens[a.currIndex]
		return a.currTok
	}
	return nil
}

// 获取操作优先级
func (a *AST) getTokPrecedence() int {
	if p, ok := precedence[a.currTok.Tok]; ok {
		return p
	}
	return -1
}

// 解析数字，并生成一个 NumberExprAST 节点
func (a *AST) parseNumber() NumberExprAST {
	f64, err := strconv.ParseFloat(a.currTok.Tok, 64)
	if err != nil {
		a.Err = errors.New(
			fmt.Sprintf("%v\nwant '(' or '0-9' but get '%s'\n%s",
				err.Error(),
				a.currTok.Tok,
				ErrPos(a.source, a.currTok.Offset)))
		return NumberExprAST{}
	}
	n := NumberExprAST{
		Val: f64,
	}
	a.getNextToken()
	return n
}

// 获取一个节点，返回 ExprAST
// 这里会处理所有可能出现的类型，并对相应类型做解析
func (a *AST) parsePrimary() ExprAST {
	switch a.currTok.Type {
	case Literal:
		return a.parseNumber()
	case Operator:
		// 对 () 语法处理
		if a.currTok.Tok == "(" {
			a.getNextToken()
			e := a.ParseExpression()
			if e == nil {
				return nil
			}
			if a.currTok.Tok != ")" {
				a.Err = errors.New(
					fmt.Sprintf("want ')' but get %s\n%s",
						a.currTok.Tok,
						ErrPos(a.source, a.currTok.Offset)))
				return nil
			}
			a.getNextToken()
			return e
		} else {
			return a.parseNumber()
		}
	default:
		return nil
	}
}

// 循环获取操作符的优先级，将高优先级的递归成较深的节点
// 这是生成正确的 AST 结构最重要的一个算法，一定要仔细阅读、理解
func (a *AST) parseBinOpRHS(execPrec int, lhs ExprAST) ExprAST {
	for {
		tokPrec := a.getTokPrecedence()
		if tokPrec < execPrec {
			return lhs
		}
		binOp := a.currTok.Tok
		if a.getNextToken() == nil {
			return lhs
		}
		rhs := a.parsePrimary()
		if rhs == nil {
			return nil
		}
		nextPrec := a.getTokPrecedence()
		if tokPrec < nextPrec {
			// 递归，将当前优先级+1
			rhs = a.parseBinOpRHS(tokPrec+1, rhs)
			if rhs == nil {
				return nil
			}
		}
		lhs = BinaryExprAST{
			Op:  binOp,
			Lhs: lhs,
			Rhs: rhs,
		}
	}
}

// AST 生成器结构体
type AST struct {
	// 词法分析的结果
	Tokens []*Token
	// 源字符串
	source string
	// 当前分析器分析的 Token
	currTok *Token
	// 当前分析器的位置
	currIndex int
	// 错误收集
	Err error
}

func MakeFunction(exp string) (result int) {
	// input text -> []token
	tokens, err := Parse(exp)
	if err != nil {
		fmt.Println("ERROR: " + err.Error())
		return
	}
	// []token -> AST Tree
	ast := NewAST(tokens, exp)
	if ast.Err != nil {
		fmt.Println("ERROR: " + ast.Err.Error())
		return
	}
	// AST builder
	ar := ast.ParseExpression()
	if ast.Err != nil {
		fmt.Println("ERROR: " + ast.Err.Error())
		return
	}
	// 加入下面的代码
	// AST traversal -> result
	result = int(ExprASTResult(ar))
	return
}
